package algorithm_primary.studyClass.新手课程.两个链表合并;

/**
 * @author mengHao.heng
 * @date 2023/6/28 16:38
 * @description MergeNode
 * <p>
 * 给定两个有序链表的头结点head1和head2
 * 返回合并之后的大链表   要求依然有序
 * 例子    1->5->7
 * 2->3->7
 * 返回    1->2->2->3->3->3->3->5->7
 *
 *
 */
public class MergeNode {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(3);
        node1.next.next = new Node(3);
        node1.next.next.next = new Node(5);
        node1.next.next.next.next = new Node(7);
        Node node2 = new Node(2);
        node2.next = new Node(2);
        node2.next.next = new Node(3);
        node2.next.next.next = new Node(3);
        node2.next.next.next.next = new Node(7);
        node1 = MergeTwoNode(node1, node2);
        System.out.println("node1 = " + node1);
    }

    /**
     * 开始合并两个链表
     *
     * @param node1
     * @param node2
     * @return
     *思路： 先拿两个进行一起循环   其中有个pre参数代表当前所有循环过的数谁是最小
     * 每一次都会比较两个节点的
     */
    private static Node MergeTwoNode(Node node1, Node node2) {
        // 找到两个节点头是最小的节点
        Node minHead = node1.value >= node2.value ? node2 : node1;
        //因为前边已经比较过谁是最小的节点了 所以那个节点可以给后走一步接着比较
        Node cur1 = minHead.next;
        // 找出谁是大头的节点
        Node cur2 = minHead == node1 ? node2 : node1;
        // pre永远指向的是当前最小的节点  刚刚已经比较一个小头的节点所以这里给pre
        Node pre = minHead;
        while (cur1 != null && cur2 != null) {
            // 比较两个节点的值  如果小头的节点还是小  那么将小头的这个节点给pre因为这个节点是目前这个循环中最小的节点 这时候给pre
            // 并且将小头的下一个节点接着循环
            if (cur1.value <= cur2.value) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                // 如果大头的节点这时候比较小  那么将节点给pre的下一个节点  因为pre代表的是上一次最小的   这一次最小的节点给上一次最小的节点的next
                pre.next = cur2;
                // 节点循环下一个节点
                cur2 = cur2.next;
            }
            // pre指向当前最小大额节点
            pre = pre.next;
        }
        //两个都不为null的好了以后判断是否还有一个长的节点没有循环完直接给上一次最小节点的下一个节点
        pre.next = cur1 == null ? cur1 : cur2;
        return minHead;
    }
}
